// amazon.cpp
// Written by Jaeseok Kim (jseokkim@hotmail.com)
// 03/29/2010

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <ext/hash_map>
#include <vector>
#include <algorithm>
#include "date.h"

using namespace std;
using namespace __gnu_cxx;

// Hashtable for sum of purchase amount in terms of CustomerID
typedef hash_map<int, double> HashCustomerPurchase;

// Pair (CustomerID, PurchaseAmount) data structure used to find 1000 largest purchases and to sort by descending order
struct PurchaseByCustomer
{
    PurchaseByCustomer(int nCustId, double dPurchase) : nCustomerId(nCustId), dPurchaseInDollars(dPurchase){}
    // Used to compare elements for sort algorithm
    bool operator() (const PurchaseByCustomer pc1, const PurchaseByCustomer pc2){return (pc1.dPurchaseInDollars > pc2.dPurchaseInDollars);}

    int nCustomerId;
    double dPurchaseInDollars;
};

class CustomerPurchaseStats
{
public:
    CustomerPurchaseStats(){}
    void addPurchase(int, double);
    int getTopPurchase(int nTop = 1000, double dMin = 100);
    int partition(int, int, double);
    bool empty() const {return Hash.empty() && Array.empty();}
    void print(int nLength = 20){
        Hash.empty() ? printArray(nLength) : printHash(nLength);
    }
    void printHash(int);
    void printArray(int);

private:
    void convertHashToArray();

    HashCustomerPurchase Hash;
    vector<PurchaseByCustomer> Array;
};

void CustomerPurchaseStats::addPurchase(int nCustomerId, double dPurchaseInDollars)
{
    // Look for existing customer ID
    HashCustomerPurchase::iterator i = Hash.find(nCustomerId);
    
    if (i == Hash.end())
    {
        // Insert a new customer ID and purchase amount
        Hash[nCustomerId] = dPurchaseInDollars;
    }
    else
    {
        // Add purchase amount to current amount
        i->second += dPurchaseInDollars;
    }
}

void CustomerPurchaseStats::convertHashToArray()
{
    // Move Hashtable to Array without increasing peak memory usage
    for (HashCustomerPurchase::iterator i = Hash.begin(); i != Hash.end();)
    {
        Array.push_back(PurchaseByCustomer(i->first, i->second));
        Hash.erase(i++);
    }
}

int CustomerPurchaseStats::getTopPurchase(int nTop, double dMin)
{
    int nTopWithMin = nTop;
    
    // Convert Hash to Array
    convertHashToArray();

    // Selection algorithm to get top purchase customers satisfying minimum value
    for (int nBgn = 0, nEnd = Array.size() - 1, nMiddle; nBgn < nEnd; )
    {
        nMiddle = partition(nBgn, nEnd, dMin);

        if (nMiddle < 0)
        {
            return -1;
        }

        if (nMiddle < nTop)
        {
            if (Array[nMiddle].dPurchaseInDollars >= dMin)
            {
                nBgn = nMiddle + 1;
            }
            else
            {
                //cout << "Number of top items: " << nMiddle << endl;
                // The number of found largest purchases are less than nTop
                nTopWithMin = nMiddle;
                break;
            }
        }
        else
        {
            nEnd = nMiddle - 1;
        }
    }
    
    // Sort the found largest purchases by descending order of purchase amount
    sort(Array.begin(), Array.begin() + nTopWithMin, Array[0]);
    
    // print the found largest purchase
    print(nTopWithMin);
    
    return nTopWithMin;
}

int CustomerPurchaseStats::partition(int nBgn, int nEnd, double dMin)
{
    if (nBgn > nEnd)
    {
        return -1;
    }

    int nSrc, nDst;
    double dPivot = max(Array[nEnd].dPurchaseInDollars, dMin);

    for (nSrc = nDst = nBgn; nSrc < nEnd; nSrc++)
    {
        if (Array[nSrc].dPurchaseInDollars > dPivot)
        {
            swap(Array[nSrc], Array[nDst++]);
        }
    }

    swap(Array[nDst], Array[nEnd]);
    
    return nDst;
} 

void CustomerPurchaseStats::printHash(int nLength)
{
    for (HashCustomerPurchase::iterator i = Hash.begin(); nLength > 0 && i != Hash.end(); nLength--, i++)
    {
        cout << i->first << " " << i->second << endl;
    }
}

void CustomerPurchaseStats::printArray(int nLength)
{
    for (int n = 0; n < nLength && n < (int)Array.size(); n++)
    {
        cout << Array[n].nCustomerId << " " << Array[n].dPurchaseInDollars << endl;
    }
}

class FileReader
{
public:
    FileReader(){}
    FileReader(const Date InputDate){LastDate = InputDate.isValidDate() ? InputDate : LastDate;}
    void loadLogFiles(int nDays = 7);
    void printTopPurchase(int nTop = 1000, double dMin = 100){Stats.getTopPurchase(nTop, dMin);}
    bool empty() const {return Stats.empty();}
    void print(int nLength = 20){Stats.print(nLength);}
    
private:
    Date LastDate;
    CustomerPurchaseStats Stats;
};

void FileReader::loadLogFiles(int nDays)
{
    if (!LastDate.isValidDate())
    {
        cout << "Not valid date" << endl;
        return;
    }
    
    string sFileName;
    int nTimeStamp, nCustomerId, nPurchaseId;
    int nNumOfOpenedFiles = 0;
    double dPurchaseInDollars;

    for (int n = 0; n < nDays; n++, LastDate.prevDate())
    {
        sFileName = "purchase.log." + LastDate.toString();
        //cout << sFileName << endl;
        ifstream ifLog(sFileName.c_str());
        if (ifLog.is_open())
        {
            nNumOfOpenedFiles++;
        }
        else
        {
            // In case of file open error, continue to the next file.
            //cout << "File open error[" << sFileName << "]" << endl;
            continue;
        }

        while (!ifLog.eof())
        {
            ifLog >> nTimeStamp >> nCustomerId >> nPurchaseId >> dPurchaseInDollars;
            if (!ifLog.eof())
            {
                Stats.addPurchase(nCustomerId, dPurchaseInDollars);
            }
        }

        ifLog.close(); 
    }
    
    if (nNumOfOpenedFiles == 0)
    {
        cout << "No file found" << endl;
    }
}

int main(int argc, const char *argv[])
{
    // Check the number of input arguments
    if (argc != 2)
    {
        cout << "Usage: " << argv[0] << " YYYY-MM-DD" << endl;
        return 1;
    }

    // Set end date
    Date EndDate(argv[1]);
    if (!EndDate.isValidDate())
    {
        return 2;
    }
    FileReader fr(EndDate);

    // Load 7 log files from the end date
    fr.loadLogFiles(7);

    // Display upto 1000 customers who spent 100.0 dollars in the 7 log files
    if (!fr.empty())
    {
        fr.printTopPurchase(1000, 100.0);
    }

    return 0;
}
